package leetcode.biweekly.week79;

import java.util.Arrays;

//Solution3Test
public class Solution3 {

	// Solution3Test
	public long maximumImportance(int n, int[][] roads) {
		int len = roads.length;
		int[] ins = new int[n];
		for (int i = 0; i < len; i++) {
			int[] r = roads[i];
			int a = r[0], b = r[1];
			ins[a]++;
			ins[b]++;
		}
		Arrays.sort(ins);
		long num = n;
		long ans = 0;
		for (int i = n - 1; i >= 0; i--) {
			ans += num * ins[i];
			num--;
		}
		return ans;
	}

}
